package gold.digger;

import gold.utils.InputUtil;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC1482 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int minDays(int[] bloomDay, int m, int k) {
            if (m * k > bloomDay.length) return -1;
            int left = 1, right = 1000000000;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (canMakeBouquet(bloomDay, m, k, mid)) {
                    // current mid is long, can make right smaller.
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }

            return left;
        }

        public boolean canMakeBouquet(int[] bloomDay, int m, int k, int day) {
            Map<Integer, Integer> cnt = new HashMap<>();
            int lastBloomIdx = 0, i = 0;
            while (i <= bloomDay.length) {
                if (i == bloomDay.length || bloomDay[i] > day) {
                    // current i flower doesn't bloom.
                    int interval = i - lastBloomIdx;
                    cnt.put(interval, cnt.getOrDefault(interval, 0) + 1);
                    while (i < bloomDay.length && bloomDay[i] > day) i++;
                    lastBloomIdx = i;
                    if (i >= bloomDay.length) break;
                } else {
                    ++i;
                }
            }

            for (Integer interval : cnt.keySet()) {
                if (interval >= k) {
                    m -= cnt.get(interval) * (interval / k);
                    if (m <= 0) return true;
                }
            }

            return m <= 0;
        }
    }

    public void run() {
        Solution solution = new Solution();
//        int[] arr = InputUtil.toIntegerArray("[1,10,3,10,2]");
//        System.out.println(solution.minDays(arr, 3, 1));

//        int[] arr = InputUtil.toIntegerArray("[1,10,3,10,2]");
//        System.out.println(solution.minDays(arr, 3, 2));

//        int[] arr = InputUtil.toIntegerArray("[7,7,7,7,12,7,7]");
//        System.out.println(solution.minDays(arr, 2, 3));

//        int[] arr = InputUtil.toIntegerArray("[1000000000,1000000000]");
//        System.out.println(solution.minDays(arr, 1, 1));

        int[] arr = InputUtil.toIntegerArray("[1,10,2,9,3,8,4,7,5,6]");
        System.out.println(solution.minDays(arr, 4, 2));

    }

    public static void main(String[] args) throws Exception {
        LC1482 an = new LC1482();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
